﻿//给你一个字符串 s，找到 s 中最长的 回文 子串。
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//输入：s = "cbbd"
//输出："bb"
//
//提示：
//	1 <= s.length <= 1000
//	s 仅由数字和英文字母组成

class Solution {
public:
    string longestPalindrome(string s) {
        // 中⼼扩展算法

        int begin = 0, len = 0, n = s.size();
        for (int i = 0; i < n; i++) // 依次枚举所有的中点

        {
            // 先做⼀次奇数⻓度的扩展

            int left = i, right = i;
            while (left >= 0 && right < n && s[left] == s[right]) {
                left--;
                right++;
            }
            if (right - left - 1 > len) {
                begin = left + 1;
                len = right - left - 1;
            }
            // 偶数⻓度的扩展

            left = i, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right]) {
                left--;
                right++;
            }
            if (right - left - 1 > len) {
                begin = left + 1;
                len = right - left - 1;
            }
        }
        return s.substr(begin, len);
    }
};